The present invention relates to the field of network management in general and specifically to the improvement of communications in a local area network containing a number of bridges.
Networks are used to interconnect sources and receivers of data. For purposes of this invention, the nature of the data sources and receivers is not important, and all of such sources and receivers will be called "end nodes." Networks provide a capability for end nodes to send messages to each other.
A basic type of is called a local area network or LAN. A LAN contains end nodes and some means for transmission between the end nodes, such as one or more wires interconnecting the nodes. In a LAN, messages between end nodes need only include a source identifier, a destination identifier, data to be transmitted, and other desired "overhead" such as network management information or error detection codes.
Sometimes networks such as LANs need to be interconnected. Such interconnection could occur if a network was to be extended or connected to dissimilar networks. Interconnection of the networks can involve the creation of a higher level network or, as long as the interconnection is not too extensive, the joining of networks at the same level.
If a higher level network is created, certain devices called "routers" must be used. Routers, however, add another layer of communication protocol and end node messages must include information to reflect the added protocol.
If networks are to be interconnected at the same level, then bridges are used to join the networks. With bridges, the end node messages need not contain additional protocol information. Ideally, bridges should be transparent to end nodes so that interconnected networks appear as one large network. An IEEE 802.1 Media Access Control Bridge Standard (Rev. E) (hereinafter "IEEE standard"), which is incorporated herein by reference, has decided that transparent bridges are to be standard for all IEEE 802 local area networks.
Basic bridge operation is explained in Backes, "Transparent Bridges for Interconnection of IEEE 802 LANs," IEEE Network, Vol. 2, No. 1, pp. 5-9 (January, 1988), which is herein incorporated by reference. Each bridge's major function is to receive messages (also called "frames") from one network connected to the bridge and to forward those messages to one or more other networks also connected to the bridge. Each bridge must therefore examine the destination addresses of the received messages. If the bridge recognizes a message's destination address as already stored in some data base inside the bridge, the bridge forwards the message to the networks indicated by that data base. If the bridge does not recognize a particular destination address, the bridge forwards the message to all of the other networks connected to it.
The bridges develop their data bases by also examining the source addresses of the messages received. When a bridge receives a message from one network, it determines that, barring other circumstances such as contradictory information, the end node specified in the source identifier may be reached via the network from which the message is received.
The network from which the message was received is called the "station address" for the source end node, and the data base is a collection of end nodes and corresponding station addresses. The station address for an end node does not indicate that the corresponding end node is on the network specified by the station address. For example, a message may have been received from a source end node on a different network, and the message may have been forwarded to the station address network by another bridge. The station address only indicates that the identified end node may be reached in the direction of the network from which the message was received.
Although bridged networks generally work quite well, their operation breaks down if there is some sort of a loop. A loop exists when two networks are connected by more than one bridge.
Loops occur either accidentally, for example because of poor bridge design, or can sometimes be designed into a network topology to provide either redundancy or backup.
In a loop situation, one of the bridges, called a first bridge, sends a message from a first network to a second network. That first bridge then records in its data base that the station address for the source of the message is the first network. When another bridge, called the second bridge, receives that forwarded message on the second network, the second bridge determines that the station address of source for the message is the second network. The second bridge then forwards the message back to the first bridge. This forwarding process will continue indefinitely without some sort of safeguard.
FIG. 1 illustrates how loops occur in interconnected networks. FIG. 1 shows networks 110, 120, 130, 140, 150, 160, 170, 180, 183, 186, 190, and 196. End nodes 111 and 112 are connected to network 110; end nodes 121 and 122 are connected to network 120; end nodes 131 and 132 are connected to network 130; end nodes 141 and 142 are connected to network 140; end nodes 151 and 152 are connected to network 150; end node 161 is connected to network 160; end node 171 is connected to network 170; end node 181 is connected to network 180; end node 184 is connected to network 183; end node 187 is connected to network 186; and end node 191 is connected to network 190. Bridges 115, 125, 135, 145, and 155 interconnect the different networks. Bridges 115 and 125 interconnect networks 110 and 120; bridge 135 interconnects networks 130 and 140; bridge 145 interconnects networks 120, 150, 160, 180, 190, and 196; and bridge 155 interconnects networks 130, 170, 183, 186, 190, and 196.
In the network topology shown in FIG. 1, several loops already exist. For example, there is a loop involving networks 110 and 120 and bridges 115 and 125, and another loop involving networks 190 and 196 through bridges 145 and 155.
To avoid the problems with loops, a mechanism must be devised either to resolve the loops or to avoid them. One method which has been devised and is described in detail in both the Backes article and the IEEE standard is the spanning tree algorithm. Generally, this algorithm involves ordering the bridges according to some criterion. Then, one bridge connected to each network is chosen as a designated bridge according to the ordering criterion, and only the designated bridge can forward messages to and from the network for which it is a designated bridge. Use of this algorithm thus breaks any loops. The other bridges connected to a network are called daughter bridges, and they forward messages to the designated bridge on only one network.
The spanning tree algorithm in this form, however, creates an additional problem. If messages are forwarded on only one of the trunked networks, congestion may result.
One way to relieve the congestion in networks created by the spanning tree algorithm is to distribute messages from daughter bridges to designated bridges across all of the common networks in a round-robin, or similar algorithm. The problem with this method is that it does not preserve the time sequence of messages.
"Time sequence of messages" refers to the order in which messages are sent from one end node to another end node. Time sequence is important because the data sent between end nodes may be spread across several messages. If the messages are received out of order, the data may be garbled. When using the roundrobin algorithm, the time sequence of messages cannot be guaranteed because messages may have different sizes and be transmitted at different rates which could disrupt the order of their transmission.
Another problem with the round-robin algorithm occurs if end nodes are located on some of the common networks. In such a situation, one cannot guarantee that messages to end nodes on one common network will be delivered if the daughter bridge's roundrobin algorithm routes those messages to a different common network.
It is therefore desirable to relieve congestion in networks, especially with congestion caused due to the use of the spanning tree algorithm. It is also desirable to maintain the time sequence of the messages when relieving the congestion and to ensure that the relief does not degrade network performance in other areas. One of those areas is the transparent operation of the networks in the spanning tree algorithm. Another area is the proper access to all the end nodes.
Additional desirable goals and benefits of the present invention will be set forth in part in the description which follows and in part will be obvious in that description or may be learned by practice of the invention.